// NC52.括号序列
// https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2 queue 队列
// 注意 pop前 front前 back后 push后 stack 栈 top/pop
//给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
//括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
//输入 "([)]"
//返回值 false

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

class Solution {
 public:
  bool isPair(char chl, char chr) {
    if ((chl == '(' && chr == ')') || (chl == '[' && chr == ']') ||
        (chl == '{' && chr == '}')) {
      return true;
    }
    return false;
  }
  bool isValid(string s) {
    // write code here
    if (s.length() == 0) {
      return true;
    }
    stack<char> skChar;
    for (int i = 0; i < s.length(); i++) {
      char ch = s[i];
      switch (ch) {
        case '(':
        case '[':
        case '{':
          skChar.push(ch);
          break;
        case ')':
        case ']':
        case '}': {
          char chl = 0;
          if (!skChar.empty()) {
            chl = skChar.top();
            skChar.pop();
          }

          bool bret = isPair(chl, ch);
          if (bret == false) {
            return false;
          }
        } break;
        default:
          break;
      }
    }
    if (skChar.empty()) {
      return true;
    }
    return false;
  }
};
